链表的倒数第N个结点

发表于 | 分类于 |
字数统计: 584 字 | 阅读时长 ≈ 2 分钟

题目描述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

 

示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

方法一：快慢指针

设置两个指针slow、fast,设链表节点数为n。求倒数第k个节点，我们先让fast走k个节点(一次一步)。然后fast和slow再同时走(一次一步)，fast走到终点走过的距离为n-k,那么slow也走了n-k,所以此时slow距离尾部距离为n - (n - k) = k。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode getKthFromEnd(ListNode head, int k) {
    if(head == null || k == 0) return null;
    ListNode fast = head, slow = head;
    while(k-- > 0) {
      fast = fast.next;
    }
    while(fast != null) {
      slow = slow.next;
      fast = fast.next;
    }
    return slow;
  }
}
var getKthFromEnd = function(head, k) {
  if(head === null || k === 0) return null
  let fast = head, slow = head
  while(k--) {
    fast = fast.next
  }
  while(fast) {
    slow = slow.next
    fast = fast.next
  }
  return slow
};

复杂度分析

  • 时间复杂度：O(n)，总体看， fast走了 N 步， slow走了 (N−k) 步
  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：36.2 MB, 在所有 Java 提交中击败了68.43%的用户

方法二：栈

把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
  public ListNode getKthFromEnd(ListNode head, int k) {
    if(head == null || k == 0) return null;
    Stack<ListNode> stack = new Stack<>();
    ListNode cur = head;
    while(cur != null) {
      stack.push(cur);
      cur = cur.next;
    }
    ListNode res = null;
    while(k-- != 0) {
      res = stack.pop();
    }
    return res;
  }
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了12.10%的用户

  • 内存消耗：36.2 MB, 在所有 Java 提交中击败了63.30%的用户